Gradient Boosting Decision Tree 简介

总体概览

本文材料基本选自台湾大学林轩田的机器学习技法课程.

  • AdaBoost Decision Tree 回顾
  • AdaBoost 的优化问题
  • Gradient Boosting

AdaBoost Decision Tree 回顾

基本算法

给定训练数据集D, 设一共建T棵树.

For t = 1, 2, … T

  • 从数据集D中,对每个样本计算权重u(t)
  • 用加权后的样本数据来计算得到一个决策树DTree(D,u(t))
  • 对获得的决策树计算其投票权重

最后对所有获得的决策树进行加权线性合并.

样本权重的选择

  • 样本的初始权重为均匀分布,每个样本权重都为1/N
  • 定义缩放因子 t=1ϵϵ
  • 错误样本的权重乘以缩放因子 ut+1n=utnt
  • 而正确样本的权重要除以缩放因子 ut+1n=utn/t

线性合并的权重

对于某个弱分类器,这里也就是一个限制了高度的树,其在最后线性合并时的权重为

αt=ln(t)

AdaBoost 的优化问题

代价函数(错误度量)的问题.

定义一个二分类问题第n个样本的真实输出标签为yn[1,1], 在AdaBoost聚合时第t个分类器的输出为gt(xn)

可以将样本权重的两个更新公式直接合并为一个公式

ut+1n=utnyngt(xn)t

更新权重的定义 αt=ln(t)

于是 t=exp(αt)

导出 ut+1n=utnexpynαtgt(xn) ut+1n=u1nTt=1expynαtgt(xn)=1NexpynTt=1αtgt(xn)

Tt=1αtgt(x),就是直到t轮的合并结果,记为voting score,即投票分数.记为s

则第t+1轮样本点n的权重就为下式

ut+1n=1Nexpynsn

回到一个基本的问题,我们需要什么样的ut+1n, 或者说我们要什么样的所有样本点权重之和Nn=1utn. 是越来越大,还是越来越小. 很简单, 随着弱分类器的增加组合,分对样本会越来越多, Training Error也会越来越小, 我们要的这个样本点权重之和也要越来越小. 如果这个样本点权重之和停止减小, 也意味着Training Error会停止减小.

于是整个问题就成为一个最小化问题

argmin(Nn=1uT+1n)=argmin(Nn=11NexpynTt=1αtgt(xn))=argmin(Nn=11Nexpynsn)

如果我们新加入一个分类器h并给一个权重η 下面的函数就可以作为代价函数在进行优化.

minhEADA=Nn=11Nexpyn(Tt=1αtgt(xn)+ηh(xn))

也就是说找到一个h(x)和一个η在最小化上面的error函数, 首先将上式简化为

EADA=Nn=1utnexpynηh(xn)

最优新添加的函数

也就是寻找h(xn)其能最小化EADA

EADA在原点处,做一阶泰勒展开来近似

minhEADA=Nn=1utnexpynηh(xn)Nn=1utn(1ynηh(xn))=Nn=1utn+Nn=1utn(yn)ηh(xn)

utn是由上一轮计算出的, 此时为常数,所以就只需要最小化ηNn=1utn(yn)h(xn), 在优化h(xn)时,η可以认为是常数, 此时最优的h(xn)就应能最小化Nn=1utn(yn)h(xn)

对于二分类问题

Nn=1utn(yn)h(xn)=Nn=1utn{1ifyn=h(xn)+1ifynh(xn)=Nn=1utn+Nn=1utn{0ifyn=h(xn)2ifynh(xn)=Nn=1utn+2Eutin

最后, 要选择h(xn)让上式最小化, 也就是选择h(xn)Eutin最小. 换言之,就是新生成的树在ut为样本权重时训练错误(training error)最小的树. 这个树在AdaBoost Decision Tree中就是第t轮生成的gt(x).

最优的新加树的权重

在找到最优的h(xn)=gt(xn)之后,就要决定η能最小化我们的代价函数.

minηEADA=Nn=1utnexpynηgt(xn)

对上面的代价函数分两种情况并重写得到下面的式子

yn=gt(xn):utexpηyngt(xn):utexpηEADA=(Nn=1utn)((1ϵt)exp(η)+ϵtexp(η))

上式对η求偏导并设为0,可以解得η

EADAη=0(1ϵt)expη+ϵtexpη=0ϵt(expη)2=1ϵtη=ln(1ϵtϵt)

最优的权重就是AdaBoost在t轮计算得到的gt(xn)的权重αt=ln(1ϵtϵt)

小结

对AdaBoost的优化问题,只是从梯度下降优化的视角来看待AdaBoost在线性加权弱分类树这一做法的合理性和最优性.

小结一下, 一共三点

  • 在AdaBoost中对应的代价函数(错误度量函数)就是所有样本点权重之和. 在t轮之后的残余错误越大,对应的下一轮的Nn=1ut+1n也就越大,目标就是不断优化减小这个所有样本点权重之和.
  • 对代价函数做一阶泰勒展开后,证明第t轮最优的新添加树,就是在AdaBoost Decision Tree中, 根据第t轮样本权重ut训练的树gt(xn)
  • 用Steepest Gradient Descent,也就是求一阶偏导为0是的η,证明对t轮新加入的树的最优合并权重就是AdaBoost Decision Tree用的αt=ln(1ϵtϵt)

Gradient Boost Desicion Tree

在AdaBoost的优化问题中,给出了一个聚合模型的代价函数和用梯度下降的方式(Steepest Descent)来优化代价函数的方式. 实际上, 对于不同的问题,譬如回归问题,多类分类问题,可以将AdaBoost Decision Tree一般化来采用不同的代价函数, 并在每一轮用残差,(注意,这里使用残差), 来对新加入的弱分类树或弱回归树,用梯度下降的方法求合并权重. 可以用来解决回归,多类分类等等不同问题. 对于二分类实际上也可以用logistic regression的代价函数来解决(AdaBoost Descision Tree采用了一种特殊的代价函数). 用这种方式扩展后就形成了Gradient Boost Decision Tree. 实际上被聚合的也不一定是树. 也就是Err函数和h(xn)都可以被一般化.

Gradient Boosting 的回归优化问题

下面还是以弱回归树用Gradient Descent聚合的方式来看看Gradient Descent Descision Tree如何处理回归问题. 采用最小均方差为代价函数.

AdaBoost的优化问题

minηmingt1NNn=1e(ynt1τ=1ατgτ(xn)+ηgt(xn))

Gradient Boost的优化问题

minηmingt1NNn=1err(t1τ=1ατgτ(xn)+ηgt(xn),yn)

对于回归问题,我们用均方差为错误(代价函数) err(s,y)=(sy)2

sn=t1τ=1ατgτ(xn),即前t-1个弱回归器对第n个样本的线性加权后的估计值

新加入的回归器的优化问题

思路上有两个,结果没区别. 

第一个思路

对Err函数做一阶泰勒展开 mingt1NNn=1err(t1τ=1ατgτ(xn)+ηgt(xn),yn)mingt1NNn=1err(sn,yn)+1NNn=1ηgt(xn)err(s,yn)sn=mingtconstants+ηNNn=1gt(xn)2(snyn)

由于第一项是常数,实际问题就等价于 mingtηNNn=1gt(xn)2(snyn)

加入正则项Regularization,来约束gt, 将优化问题改写为

mingtηNNn=1(gt(xn)2(snyn)+gt(xn)2)=mingtηNNn=1(constant+(gt(xn)(ynsn))2)mingtηNNn=1(gt(xn)(ynsn))2

结论,最优的gt就是一个对残差(ynsn)进行回归的回归器. 例如用CART树进行回归.

个人思考, 这个思路很绕. 同时不加入正则项,下面的式子就不好优化

mingtηNNn=1gt(xn)2(snyn)

而为什么正则项的大小为1NNn=1ηgt(xn)2我认为

  • 还是为了后续的推导方便.
  • 不需要强回归器

第二个思路

第一个思路中的正则项把我绕了半天. 实际上考虑问题可以有下面简洁的思路.

mingt1NNn=1err(t1τ=1ατgτ(xn)+ηgt(xn),yn)=mingt1NNn=1err(sn+ηgt(xn),yn)=mingt1NNn=1(sn+ηgt(xn)yn)2=mingt1NNn=1(ηgt(xn)(ynsn))2

上面的式子很容易推导,结论也很清晰就是对残差ynsn的回归, 稍微麻烦的是除了gt(xn)还有一个η.

转换一下思路,此时即没有gt(xn)也没有有η, 我们实际上应该做的就是构建一个回归器来对残差回归. 也就是设η=1,也可以想象新的回归器就是ηgt(xn). 当然新的回归器构建好之后在下一步来重新计算新的回归器的权重η

在AdaBoost中也是同样的思路, 直接用残差构建下一个分类器, 然后再计算新的分类器的权重. 在AdaBoost残差就是下一轮的样本点权重和

新加入的回归器的权重

当有了gt(x)η的计算就变的简单了,同AdaBoost的优化过程的说明, 用Steepest Descent对η求偏导并设为0,可以解得η

minη1NNn=1(ηgt(xn)(ynsn))21NNn=12(ηgt(xn)(ynsn))gt(xn)=0η=Nn=1gt(xn)(ynsn)Nn=1gt(xn)2

小结

GBDT 是对AdaBoost DT的一般性扩展,支持任意的代价函数,支持不同分类器或回归器,以回归树为例,计算过程如下

  • 初始化s0,s1,sn=0 也就是初始的残差ynsn=yn
  • for t=1 … T
  • 用{xn,(ynsn)}构建回归树gt. 例如 bagging采样后训练的裁剪过的CART树
  • 计算回归树的权重ηt,这一步与代价函数相关.
  • 更新sn=sn+ηtgt(xn)
  • end for
  • 最后返回G(x)=Tt=1ηtgt(x)

最后

前两年开始出现的xgboost(extreme gradient boosted tree)十分强悍. 本质思路上同GBDT或者说GBM.

下面贴些别人在网上贴的关于xgboost的说法,来自http://www.jianshu.com/p/2a167d789b73, ()中的为个人理解和猜测

  • xgboost在目标函数中加入了正则化项(这个正则项应该与GBDT的有所不同)
  • xgboost在迭代优化的时候使用了目标函数的泰勒展开的二阶近似,paper中说能加快优化的过程
  • Shrinkage(缩减),相当于学习速率(xgb中的eta),xgb在进行完一次迭代后,会将叶子节点的权重乘上该系数,主要是为了削弱各棵树的影响,让后面有更大的学习空间. (思路上没问题,对于GBDT或者GBM来说也应当是弱分类器或弱回归器的加权组合,不要用强分类器来组合)
  • 列抽样(column subsampling),xgb借鉴了rf的做法,支持列抽样,不仅能降低过拟合,还能减少计算. (恩,除了对样本的采样,也对样本的特征进行采样,不过貌似GBDT也应该容易加入这个)
  • 对于特征的值有缺失的样本,xgb可以自动学习出它的分裂方向
  • xgb支持并行,在特征粒度上并行,xgboost在训练之前,预先对数据进行排序,然后保存为block结构,后面的迭代中重复地使用这个结构,大大减小计算量,这个block结构也使得并行成为了可能,在进行节点分裂时,需要计算每个特征的增益,最终选择增益最大的那个特征去做分裂,那么各个特征的增益计算就可以并行化
  • 可并行的近似直方图算法。树节点在进行分裂时,需要计算每个特征的每个分裂点对应的增益,即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下,贪心算法效率会变得很低,所以xgb还提出了一种可并行的近似直方图算法,用于高效地生成候选的分割点

我个人用过xgboost几次,感觉很好用,速度也很快. 强烈推荐使用xgboost.